package com.imagination.applet;

import com.imagination.applet.infrastructure.Node;

public class Solution {

    public Node<?> generateTree(int n) {
        if (n <= 0) {
            return null;
        }
        Node root = new Node();
        root.setData(1);
        recurse(root, 1, n);
        return root;

    }

    private void recurse(Node node, int level, int max) {
        if (level >= max) {
            return;
        }
        Node left = new Node();
        node.setLeft(left);
        left.setParent(node);
        left.setData((int) node.getData() * 2);
        recurse(left, level + 1, max);

        Node right = new Node();
        node.setRight(right);
        right.setParent(node);
        right.setData((int) node.getData() * 2 + 1);
        recurse(right, level + 1, max);

    }

    public void roadPath(Node node, Node start, Node startStart) {
        if (node == null) {
            return;
        }
        System.out.println(node.getData());
        Node left = node.getLeft();
        if (left != null && left != start) {
            roadPath(left, node, start);
        }
        Node right = node.getRight();
        if (right != null && right != start) {
            roadPath(right, node, start);
        }
        Node parent = node.getParent();
        if (parent != null && parent != start && parent != startStart) {
            roadPath(parent, node, start);
        }
    }

    public static void main(String[] args) {
        Solution s = new Solution();
        Node root1 = s.generateTree(4);
        Node root2 = s.generateTree(4);
        Node root3 = s.generateTree(4);
        root1.setParent(root2);
        ;
        root2.setParent(root3);
        root3.setParent(root1);

        s.roadPath(root1.getRight().getLeft(), null, null);
//        System.out.println(n.getLeft());
//        System.out.println(n.getRight());


        //6
        //12
        //13
        //3
        //7
        //14
        //15
        //1
        //2
        //4
        //8
        //9
        //5
        //10
        //11
        //1
        //2
        //4
        //8
        //9
        //5
        //10
        //11
        //3
        //6
        //12
        //13
        //7
        //14
        //15
        //1
        //2
        //4
        //8
        //9
        //5
        //10
        //11
        //3
        //6
        //12
        //13
        //7
        //14
        //15


    }
}
